Fixed-Parameter Tractable

释义 Definition

固定参数可解（固定参数可处理）：在参数化复杂性理论中，指一个问题若能在时间 \(f(k)\cdot n^{O(1)}\) 内求解，则称其为固定参数可解（FPT）。其中 \(n\) 是输入规模，\(k\) 是选定的参数，\(f(k)\) 只依赖于参数而与 \(n\) 无关。常用于描述“当参数较小时时，尽管总体问题可能很难，仍可高效求解”。

发音 Pronunciation (IPA)

/ˌfɪkst pəˈræmɪtər ˈtræktəbəl/

例句 Examples

This problem is fixed-parameter tractable when parameterized by solution size.
当以解的大小作为参数时，这个问题是固定参数可解的。

Although the general problem is NP-hard, it becomes fixed-parameter tractable on graphs of bounded treewidth.
虽然一般情形下该问题是 NP-困难的，但在树宽有界的图上它会变成固定参数可解。

词源 Etymology

该术语来自参数化算法（parameterized algorithms）与参数化复杂性（parameterized complexity）领域：

fixed-parameter 表示“固定的参数 \(k\)”被单独拿出来影响复杂度；
tractable 意为“可处理、可在实践中有效求解”。
合起来强调：复杂度允许对参数呈现较“昂贵”的依赖（如指数），但对输入规模 \(n\) 仍保持多项式级别，从而在参数较小时仍具有可行性。

文学与著作中的用例 Literary / Notable Works